/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool IsInTree(TreeNode* root,TreeNode* x)
    {
        if(root==nullptr) return false;
        return root==x||IsInTree(root->left,x)||IsInTree(root->right,x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr) return nullptr;

        if(p==root||q==root) return root;;//其中一个是根，那就是祖先

        bool pInL=IsInTree(root->left,p);
        bool pInR=!pInL;//不在左就在右
        bool qInL=IsInTree(root->left,q);
        bool qInR=!qInL;

        if((pInL && qInR)||(pInR && qInL))//在左右子树两遍，根就是祖先
        {
            return root;
        }
        else if(pInL&&qInL)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else
        {
            return lowestCommonAncestor(root->right,p,q);
        }
    }
};

class Solution2 {
public:
    bool GetPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path)
    {
        if(root==nullptr) return false;
        
        path.push(root);
        if(root==x) return true;

        if(GetPath(root->left,x,path))
            return true;
        if(GetPath(root->right,x,path))
            return true;
        
        path.pop();
        return false;
        
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath,qPath;
        GetPath(root,p,pPath);
        GetPath(root,q,qPath);
        while(pPath.size()!=qPath.size())
        {
            if(pPath.size()>qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }
        while(pPath.top()!=qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};